Recover a tree from preorder traversal [DFS]

Time: O(N); Space: O(H); hard

We run a preorder depth first search on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. (If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)

If a node has only one child, that child is guaranteed to be the left child.

Given the output S of this traversal, recover the tree and return its root.

Example 1:

Input: S = “1-2–3–4-5–6–7”

Output: {TreeNode} [1,2,5,3,4,6,7]

Example 2:

Input: S = “1-2–3—4-5–6—7”

Output: {TreeNode} [1,2,5,3,null,6,null,4,null,7]

Example 3:

Input: S = “1-401–349—90–88”

Output: {TreeNode} [1,401,null,349,88,90]

Constraints:

• The number of nodes in the original tree is between 1 and 1000.

• Each node will have a value between 1 and 10^9.

Hints:

1. Do an iterative depth first search, parsing dashes from the string to inform you how to link the nodes together.

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Auxiliary Tools

from graphviz import Graph

class TreeTasks(object):
    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left:
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right:
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

1. Iterative stack solution

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def recoverFromPreorder(self, S):
        """
        :type S: str
        :rtype: TreeNode
        """
        i = 0
        stack = []
        while i < len(S):
            level = 0
            while i < len(S) and S[i] == '-':
                level += 1
                i += 1
            while len(stack) > level:
                stack.pop()
            val = []
            while i < len(S) and S[i] != '-':
                val.append(S[i])
                i += 1
            node = TreeNode(int(''.join(val)))
            if stack:
                if stack[-1].left is None:
                    stack[-1].left = node
                else:
                    stack[-1].right = node
            stack.append(node)
        return stack[0]

s = Solution1()
S = "1-2--3--4-5--6--7"
tree = s.recoverFromPreorder(S)
t = TreeTasks()
dot = t.visualize_tree(tree)

S = "1-2--3---4-5--6---7"
tree = s.recoverFromPreorder(S)
t = TreeTasks()
dot = t.visualize_tree(tree)

S = "1-401--349---90--88"
tree = s.recoverFromPreorder(S)
t = TreeTasks()
dot = t.visualize_tree(tree)

2. Recursive solution

class Solution2(object):
    def recoverFromPreorder(self, S):
        """
        :type S: str
        :rtype: TreeNode
        """
        def recoverFromPreorderHelper(S, level, i):
            j = i[0]
            while j < len(S) and S[j] == '-':
                j += 1

                if level != j - i[0]:
                    return None

            i[0] = j
            while j < len(S) and S[j] != '-':
                j += 1
            node = TreeNode(int(S[i[0]:j]))
            i[0] = j

            node.left = recoverFromPreorderHelper(S, level + 1, i)
            node.right = recoverFromPreorderHelper(S, level + 1, i)

            return node

        return recoverFromPreorderHelper(S, 0, [0])

S = "1-401--349---90--88"
tree = s.recoverFromPreorder(S)
t = TreeTasks()
dot = t.visualize_tree(tree)

See also:

https://leetcode.com/problems/recover-a-tree-from-preorder-traversal

https://www.lintcode.com/problem/recover-a-tree-from-preorder-traversal/description

Related problems: